import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;


public class Leetcode1765 {
    private static final int[][] AROUND = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
    };
    private static final int WATER_NUMBER = 1;

    public static void main(String[] args) {
        int[][] isWater = new int[][]{
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0}
        };
        int[][] res = highestPeak(isWater);
        for (int[] ints : res) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public static int[][] highestPeak(int[][] isWater) {
        Queue<int[]> queue = new ArrayDeque<>();
        int[][] res = new int[isWater.length][];
        boolean[][] isHandle = new boolean[isWater.length][];

        for (int i = 0; i < isWater.length; i++) {
            res[i] = new int[isWater[i].length];
            isHandle[i] = new boolean[isWater[i].length];
            for (int j = 0; j < isWater[i].length; j++) {
                if (isWater[i][j] == WATER_NUMBER) {
                    queue.add(new int[]{i, j});
                    isHandle[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] index = queue.poll();
            for (int[] ints : AROUND) {
                int x = ints[0] + index[0];
                int y = ints[1] + index[1];
                if (x < 0 || x >= isWater.length || y < 0 || y >= isWater[x].length || res[x][y] > res[index[0]][index[1]] + 1 || isHandle[x][y]) {
                    continue;
                }

                queue.add(new int[]{x, y});
                isHandle[x][y] = true;
                res[x][y] = res[index[0]][index[1]] + 1;
            }
        }

        return res;
    }
}
